{
 "cells": [
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "### Title: #Palindromic Substrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Difficulty: #Medium"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Category Title: #Algorithms"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Tag Slug: #string #dynamic-programming"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Name Translated: #字符串 #动态规划"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solution Name: countSubstrings"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Title: #回文子串"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Translated Content:\n",
    "<p>给你一个字符串 <code>s</code> ，请你统计并返回这个字符串中 <strong>回文子串</strong> 的数目。</p>\n",
    "\n",
    "<p><strong>回文字符串</strong> 是正着读和倒过来读一样的字符串。</p>\n",
    "\n",
    "<p><strong>子字符串</strong> 是字符串中的由连续字符组成的一个序列。</p>\n",
    "\n",
    "<p>具有不同开始位置或结束位置的子串，即使是由相同的字符组成，也会被视作不同的子串。</p>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>示例 1：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"abc\"\n",
    "<strong>输出：</strong>3\n",
    "<strong>解释：</strong>三个回文子串: \"a\", \"b\", \"c\"\n",
    "</pre>\n",
    "\n",
    "<p><strong>示例 2：</strong></p>\n",
    "\n",
    "<pre>\n",
    "<strong>输入：</strong>s = \"aaa\"\n",
    "<strong>输出：</strong>6\n",
    "<strong>解释：</strong>6个回文子串: \"a\", \"a\", \"a\", \"aa\", \"aa\", \"aaa\"</pre>\n",
    "\n",
    "<p>&nbsp;</p>\n",
    "\n",
    "<p><strong>提示：</strong></p>\n",
    "\n",
    "<ul>\n",
    "\t<li><code>1 &lt;= s.length &lt;= 1000</code></li>\n",
    "\t<li><code>s</code> 由小写英文字母组成</li>\n",
    "</ul>\n"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Description: [palindromic-substrings](https://leetcode.cn/problems/palindromic-substrings/description/)"
   ]
  },
  {
   "cell_type": "markdown",
   "metadata": {},
   "source": [
    "Solutions: [palindromic-substrings](https://leetcode.cn/problems/palindromic-substrings/solutions/)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "test_cases = ['\"abc\"', '\"aaa\"']"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            l, r = i, i\n",
    "            while l >= 0 and r < len(s):\n",
    "                if s[l] == s[r]:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            \n",
    "            l, r = i, i + 1\n",
    "            while l >= 0 and r < len(s):\n",
    "                if s[l] == s[r]:\n",
    "                    count += 1\n",
    "                else:\n",
    "                    break\n",
    "                l -= 1\n",
    "                r += 1\n",
    "            \n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        tot=0\n",
    "        for i in range(len(s)):\n",
    "            tot+=1\n",
    "            j=1\n",
    "            while (i-j>=0) and (i+j<=len(s)-1):\n",
    "                if s[i-j]==s[i+j]:\n",
    "                    tot+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    break\n",
    "            j=0\n",
    "            while (i-j>=0) and (i+1+j<=len(s)-1):\n",
    "                if s[i-j]==s[i+1+j]:\n",
    "                    tot+=1\n",
    "                    j+=1\n",
    "                else:\n",
    "                    break\n",
    "        return tot\n",
    "        \n",
    "        \n",
    "                    \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        res = len(s)\n",
    "        for i in range(len(s)):\n",
    "            res += self.countPosition(s,i-1,i+1)\n",
    "            res += self.countPosition(s,i,i+1)\n",
    "        return res\n",
    "    \n",
    "    \n",
    "    def countPosition(self, s, left, right):\n",
    "        count = 0\n",
    "        while left >=0 and right < len(s):\n",
    "            if s[left] == s[right]:\n",
    "                count += 1\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            else:\n",
    "                break\n",
    "        return count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        count = 0\n",
    "        cache = {}\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i, len(s)):\n",
    "                sub_s = s[i:j + 1]\n",
    "                if sub_s in cache:\n",
    "                    count += 1\n",
    "                elif self.is_palindrome(sub_s):\n",
    "                    cache[sub_s] = 1\n",
    "                    count += 1\n",
    "        return count\n",
    "        \n",
    "    def is_palindrome(self, s):\n",
    "        i, j = 0, len(s) - 1\n",
    "        while i < j:\n",
    "            if s[i] != s[j]:\n",
    "                return False\n",
    "            i += 1\n",
    "            j -= 1\n",
    "        return True"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        sums = len(s)\n",
    "        r=0\n",
    "        # while(r<len(s)):\n",
    "        for r in range(len(s)):\n",
    "            l1=r-1\n",
    "            r1=r\n",
    "            l2=r-1\n",
    "            r2=r+1\n",
    "            while l1>-1 and r1<len(s):\n",
    "                if s[l1]==s[r1]:\n",
    "                    sums+=1\n",
    "                    r1+=1\n",
    "                    l1-=1\n",
    "                else:\n",
    "                    break\n",
    "            while l2>-1 and r2<len(s):\n",
    "                if s[l2]==s[r2]:\n",
    "                    sums+=1\n",
    "                    r2+=1\n",
    "                    l2-=1\n",
    "                else:\n",
    "                    break\n",
    "            \n",
    "        return sums"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countSubstrings(self, s):\n",
    "#         \"\"\"\n",
    "#         :type s: str\n",
    "#         :rtype: int\n",
    "#         \"\"\"\n",
    "#         # DP/奇数偶数字符串回文子串比对  O(n^2)处理\n",
    "#         # Manacher 算法 时间复杂度 O(N)处理\n",
    "#         sc = '#' + '#'.join(s) + '#'\n",
    "#         n = len(s)\n",
    "#         p = [0] * n\n",
    "#         _id, mx, res = 0, 0, 0\n",
    "#         for i in range(1, n - 1):\n",
    "#             if mx > i:\n",
    "#                 p[i] = min(mx - i, p[2 * _id - i])\n",
    "#             while i + p[i] + 1 < n and i - p[i] - 1 >= 0 and s[i + p[i] + i] == s[i - p[i] - 1]:\n",
    "#                 p[i] += 1\n",
    "#             if (i + p[i] > mx):\n",
    "#                 _id = i\n",
    "#                 mx = i + p[i]\n",
    "#             res += (p[i] + 1) / 2\n",
    "#         return res\n",
    "class Solution(object):\n",
    "    def countSubstrings(self, s):\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        s = '#' + '#'.join(s) + '#'\n",
    "        n = len(s)\n",
    "        p = [0]*n\n",
    "        _id = mx = res = 0\n",
    "        for i in range(1,n-1):\n",
    "            if(mx > i):\n",
    "                p[i] = min(mx-i, p[2*_id-i])\n",
    "            while i+p[i]+1 < n and i-p[i]-1 >=0 and s[i+p[i]+1] == s[i-p[i]-1]:\n",
    "                p[i] += 1\n",
    "            if(i + p[i] > mx):\n",
    "                _id = i\n",
    "                mx = i + p[i]\n",
    "            res += int((p[i]+1)/2)\n",
    "        return res\n",
    "                \n",
    "        \n",
    "        \n",
    "        \n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s):\n",
    "        if(len(s)==1):\n",
    "            return 1\n",
    "        count=0\n",
    "        for i in range(0,len(s)):\n",
    "            if(s[i:]==s[i:][::-1]):\n",
    "                count+=1\n",
    "        \n",
    "        return count+self.countSubstrings(s[:-1])\n",
    "        \"\"\"\n",
    "        :type s: str\n",
    "        :rtype: int\n",
    "        \"\"\"\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        mid=0\n",
    "        right=0\n",
    "        t='#'+'#'.join(s)+'#'\n",
    "        p=[1]*len(t)\n",
    "        for i in range(len(t)):\n",
    "            if i<right-2:\n",
    "                p[i]=min(p[2*mid-i],right-i)\n",
    "            while i-p[i]>=0 and i+p[i]<len(t) and t[i-p[i]]==t[i+p[i]]:\n",
    "                p[i]+=1\n",
    "            if i+p[i]>right:\n",
    "                right=i+p[i]\n",
    "                mid=i\n",
    "        res=0\n",
    "        for i in range(len(p)):\n",
    "            res+=p[i]//2\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# 0 n^3\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        re=0\n",
    "        n=len(s)\n",
    "        def is_pla(s):\n",
    "            return s==s[::-1]\n",
    "        for i in range(n):\n",
    "            for j in range(i,n):\n",
    "                if(is_pla(s[i:j+1])):\n",
    "                    re+=1\n",
    "        return re\n",
    "        \n",
    "input=\"aaa\"\n",
    "a=Solution()\n",
    "a.countSubstrings(input)"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        for i in range(2*n-1):\n",
    "            left, right = i//2, (i+1)//2\n",
    "            while left>=0 and right<n and s[left] == s[right]:\n",
    "                count += 1\n",
    "                left -= 1\n",
    "                right += 1\n",
    "        return count\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def __init__(self):\n",
    "        self.count = 0 # 记录回文子串数量\n",
    "\n",
    "    def expandAroundCenter(self, s, left, right):\n",
    "        while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "            self.count += 1\n",
    "            left -= 1\n",
    "            right += 1\n",
    "\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        for i in range(len(s)):\n",
    "            # 判断A B A的情况\n",
    "            self.expandAroundCenter(s, i, i)\n",
    "            # 判断A B B A的情况\n",
    "            self.expandAroundCenter(s, i, i + 1)\n",
    "        return self.count\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        self.ans = 0\n",
    "        def helper(x, y):\n",
    "            while x >= 0 and y < n and s[x] == s[y]:\n",
    "                x -= 1\n",
    "                y += 1\n",
    "                self.ans += 1\n",
    "        for i in range(n):\n",
    "            helper(i, i)\n",
    "            helper(i, i +1)\n",
    "        return self.ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "# class Solution:\n",
    "#     def countSubstrings(self, s: str) -> int:\n",
    "        # count=0\n",
    "        # l=len(s)\n",
    "        # for i in range(1,l):\n",
    "        #     if s[i-1]==\n",
    "        \n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #暴力解法，设f(i)是以第i个字符结尾的字符所有回文子串数，因此f(i) = f(i-1)+以i结尾回文子串数，直接迭代即可\n",
    "        if s == '':\n",
    "            return 0\n",
    "        end = s[-1]\n",
    "        num = 0\n",
    "        for i in range(len(s)):\n",
    "            if s[i] == end and s[i:] == s[i:][::-1]:#回文数特点就是首跟尾肯定相同，相同了再判断是否是回文数，是就+1\n",
    "                num += 1\n",
    "        return self.countSubstrings(s[:-1])+num\n",
    "\n",
    "\n",
    "# 作者：superyuki\n",
    "# 链接：https://leetcode-cn.com/problems/palindromic-substrings/solution/pythonjian-ji-di-gui-fa-fei-zhong-xin-di-gui-dong-/\n",
    "# 来源：力扣（LeetCode）\n",
    "# 著作权归作者所有。商业转载请联系作者获得授权，非商业转载请注明出处。"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        cnt=0\n",
    "        for i in range(2*n-1):\n",
    "            l=i//2\n",
    "            r=i//2+i%2\n",
    "            while l>=0 and r<n and s[l]==s[r]:\n",
    "                cnt+=1\n",
    "                l-=1\n",
    "                r+=1\n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        '''\n",
    "        def check(s1):\n",
    "            i,j=0,len(s1)-1\n",
    "            while i<j:\n",
    "                if s1[i]!=s1[j]:\n",
    "                    return False\n",
    "                i+=1\n",
    "                j-=1\n",
    "            return True\n",
    "        n=len(s)\n",
    "        if n<=1:return 1\n",
    "        ans=n\n",
    "        l=0\n",
    "        for l in range(n):\n",
    "            for r in range(l+1,n):\n",
    "                if check(s[l:r+1]):\n",
    "                    ans=ans+1\n",
    "        return ans\n",
    "        '''\n",
    "        '''\n",
    "        dp = [[False] * len(s) for _ in range(len(s))]\n",
    "        result = 0\n",
    "        for i in range(len(s)-1, -1, -1): #注意遍历顺序\n",
    "            for j in range(i, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1: #情况一 和 情况二\n",
    "                        result += 1\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i+1][j-1]: #情况三\n",
    "                        result += 1\n",
    "                        dp[i][j] = True\n",
    "        print(dp)\n",
    "        return result\n",
    "        '''\n",
    "        self.num=0\n",
    "        def echeck(left, right):\n",
    "            while left >= 0 and right < len(s) and s[left] == s[right]:\n",
    "                self.num+=1\n",
    "                left -= 1\n",
    "                right += 1\n",
    "            return\n",
    "        start, end = 0, 0\n",
    "        for i in range(len(s)):\n",
    "            echeck(i, i)\n",
    "            echeck(i, i + 1)\n",
    "        return self.num"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #中心扩展法，枚举可能的回文中心并向两端扩展\n",
    "        #例如n=4时，可能的回文中心为，00,01,11,12,22,23,33 共2n-1个\n",
    "        #时间复杂度o(n**2)\n",
    "        '''n = len(s)\n",
    "        ans = 0\n",
    "        for i in range(2*n-1):\n",
    "            l = i>>1\n",
    "            r = l+1 if i%2 else l \n",
    "            while l >=0 and r < n and s[l] == s[r]:\n",
    "                ans += 1\n",
    "                l -= 1\n",
    "                r += 1\n",
    "        return ans '''\n",
    "        \n",
    "        #manacher方法\n",
    "        myString = \"$#\"\n",
    "        for ch in s:\n",
    "            myString += ch \n",
    "            myString += \"#\"\n",
    "        myString += \"!\"\n",
    "        n = len(myString)\n",
    "        f = [0]*n\n",
    "        iMax = 0 #最远回文右端点对应的回文中心\n",
    "        rMax = 0 #最远回文右端点\n",
    "        ans = 0\n",
    "        for i in range(1,n-1):\n",
    "            if i <= rMax:\n",
    "                f[i] = min(rMax-i+1,f[2*iMax-i])\n",
    "            else:\n",
    "                f[i] = 1\n",
    "            while myString[i+f[i]] == myString[i-f[i]]:\n",
    "                f[i] += 1\n",
    "            if i+f[i]-1 > rMax:\n",
    "                rMax = i+f[i]-1\n",
    "                iMax = i \n",
    "            ans += f[i]//2\n",
    "        return ans \n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #dp[i][j]表示s[i,j+1]是否是回文子串\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        dp = [False] * n\n",
    "        \n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(n-1, i-1, -1):\n",
    "                if s[i] == s[j] and (j - i <= 1 or dp[j - 1]): \n",
    "                    dp[j] = True\n",
    "                    count += 1\n",
    "                else:\n",
    "                    dp[j] = False\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "\n",
    "        bound = len(s)\n",
    "        def gs(s, bidx, eidx, cnt):\n",
    "            while bidx>=0 and eidx<bound:\n",
    "                if s[bidx]==s[eidx]:\n",
    "                    cnt+=1\n",
    "                    bidx-=1\n",
    "                    eidx+=1\n",
    "                else:\n",
    "                    break\n",
    "            return cnt\n",
    "        \n",
    "        cnt = 0\n",
    "        for i in range(bound):\n",
    "            cnt = gs(s, i, i, cnt)\n",
    "            if i+1<bound:\n",
    "                cnt = gs(s, i, i+1, cnt)\n",
    "        return cnt\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "#统计所有回文子串的数目\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #中心拓展法\n",
    "        ans,n=0,len(s)\n",
    "        for i in range(0,2*n-1):\n",
    "            l,r=i//2,i//2+i%2\n",
    "            print(s,l,r)\n",
    "            while l>=0 and r<n and s[l]==s[r]:\n",
    "                ans+=1\n",
    "                # l,r=l+1,r-1\n",
    "                l,r=l-1,r+1#往两边拓展\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        if n < 2:\n",
    "            return 1\n",
    "        def dfs(l, r):\n",
    "            count = 0\n",
    "            temp = s[l:r+1]\n",
    "            if temp == temp[::-1]:\n",
    "                count += 1\n",
    "                if l -1 >= 0 and r + 1 < len(s):\n",
    "                    count += dfs(l-1, r+1)\n",
    "                    return count\n",
    "                else:\n",
    "                    return count\n",
    "            else:\n",
    "                return count\n",
    "        for i in range(1, n, 1):\n",
    "            ans = ans + dfs(i,i) + dfs(i-1,i)\n",
    "        return ans+1"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        h=[-1]*26\n",
    "        n=len(s)\n",
    "        l=[-1]*n\n",
    "        dp=[0]*(1+n)\n",
    "        for i in range(n):\n",
    "            l[i]=h[ord(s[i])-ord('a')]\n",
    "            h[ord(s[i])-ord('a')]=i\n",
    "            dp[i+1]=self.reversenum(l,s,i,l[i])+dp[i]+1\n",
    "        return dp[n]\n",
    "    def reversenum(self,l,s,i,start):\n",
    "        if start==-1:\n",
    "            return 0\n",
    "        if (s and s[i:start-1:-1] == s[start:i+1]) or s[i::-1] == s[start:i+1]:\n",
    "            return 1+self.reversenum(l,s,i,l[start])\n",
    "        else:\n",
    "            return self.reversenum(l,s,i,l[start])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        # res = []\n",
    "        res = 0\n",
    "        r = []\n",
    "        rr = []\n",
    "        def ishw(s):\n",
    "            return s[::-1] == s\n",
    "\n",
    "        def dfs(idx):\n",
    "            for i in range(idx, len(s)):\n",
    "                if rr and i - rr[-1] > 1:\n",
    "                    break\n",
    "                r.append(s[i])\n",
    "                rr.append(i)\n",
    "                # print(rr)\n",
    "                s_ = \"\".join(r)\n",
    "                if ishw(s_):\n",
    "                    nonlocal res\n",
    "                    res += 1\n",
    "                dfs(i+1)\n",
    "                r.pop()\n",
    "                rr.pop()\n",
    "        \n",
    "\n",
    "        dfs(0)\n",
    "        return res\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        # dp \n",
    "        # n, cnt, res = len(s), 0, []\n",
    "        # dp = [[False] * n for _ in range(n)]\n",
    "        # dp[0][0] = True\n",
    "        # for i in range(n, -1, -1):\n",
    "        #     for j in range(i, n):\n",
    "        #         if j - i == 0:\n",
    "        #             dp[i][j] = True\n",
    "        #         elif j - i == 1:\n",
    "        #             dp[i][j] = s[i] == s[j]\n",
    "        #         else:\n",
    "        #             dp[i][j] = dp[i+1][j-1] and s[i] == s[j]\n",
    "        #         if dp[i][j]:\n",
    "        #             cnt += 1\n",
    "        #             res.append(s[i:j+1])\n",
    "        # #print(res)\n",
    "        # return cnt\n",
    "\n",
    "\n",
    "        # 中心扩展法\n",
    "        n, cnt, res = len(s), 0, []\n",
    "        for i in range(n):\n",
    "            cnt += self.find(s, i, i)[0]\n",
    "            cnt += self.find(s, i, i+1)[0]\n",
    "            res.append(self.find(s, i, i)[1])\n",
    "            res.append(self.find(s, i, i+1)[1])\n",
    "        print(res)\n",
    "        return cnt    \n",
    "\n",
    "    def find(self, s, l, r):\n",
    "        cnt = 0\n",
    "        while l >= 0 and r < len(s) and s[l] == s[r]:\n",
    "            cnt += 1\n",
    "            l -= 1\n",
    "            r += 1\n",
    "        return (cnt, s[l+1: r])\n",
    "        \n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    @cache\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        if n<=1:\n",
    "            return n\n",
    "        ans=self.countSubstrings(s[:-1])\n",
    "        def check(s):\n",
    "            start,end=0,len(s)-1\n",
    "            while start<end:\n",
    "                if s[start]!=s[end]:\n",
    "                    return False\n",
    "                start+=1\n",
    "                end-=1\n",
    "            return True\n",
    "        for i in range(n):\n",
    "            if check(s[i:]):\n",
    "                ans+=1\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[False] * i for i in range(1, n+1)]\n",
    "        res = 0\n",
    "        for i in range(n):\n",
    "            for j in range(i+1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                elif j+1 == i:\n",
    "                    dp[i][j] = True if s[i] == s[j] else False\n",
    "                else:\n",
    "                    dp[i][j] = True if s[i] == s[j] and dp[i-1][j+1] else False\n",
    "                if dp[i][j]:\n",
    "                    res += 1\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = {key:[False]*(len(s)-key) for key in range(len(s))}\n",
    "        #dp = [[False]*len(s) for _ in range(len(s))]\n",
    "        ans = 0\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if (s[i] == s[j]) and ((j-i <=1) or dp[i+1][j-1-i-1]):\n",
    "                #if (j-i <=1) or dp[i+1][j-1-i-1]:\n",
    "                    dp[i][j-i] = True\n",
    "                    ans+=1\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        ans = []\n",
    "        for window in range(1, len(s)):\n",
    "            for left in range(len(s)):\n",
    "                right = left+window\n",
    "                if right>=len(s):\n",
    "                    break\n",
    "                #print(s[left:right+1], left, right)\n",
    "                while(left<right):\n",
    "                    if s[left]!=s[right]:\n",
    "                        break\n",
    "                    left+=1\n",
    "                    right-=1\n",
    "                if left==right or left-right==1:\n",
    "                    ans.append(s[left:right+1])\n",
    "\n",
    "        return len(ans)+len(s)\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        list = []\n",
    "        def ones(left):\n",
    "            for right in range(left+1,l):\n",
    "                if s[left:right+1] == s[left:right+1][::-1] and right > left :\n",
    "                    list.append(1)\n",
    "                    \n",
    "                \n",
    "        for i in range(l):\n",
    "            ones(i)        \n",
    "\n",
    "        if not list:\n",
    "            return l\n",
    "        else:\n",
    "            m = len(list)\n",
    "            return m+l"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        x=[]\n",
    "        m=[]\n",
    "        max1=0\n",
    "        for i in range(len(s)):\n",
    "            m=[]\n",
    "            if(i!=len(s)-1):\n",
    "                m.append(1)\n",
    "                max1+=1\n",
    "                if(s[i]==s[i+1]):\n",
    "                    m.append(1)\n",
    "                    max1+=1\n",
    "                else:\n",
    "                    m.append(0)\n",
    "            else:\n",
    "                m.append(1)\n",
    "                max1+=1\n",
    "            x.append(m)\n",
    "        for m in range(2,len(s)):\n",
    "            for i in range(0,len(s)-m):\n",
    "                if(s[i]==s[m+i]):\n",
    "                    if(x[i+1][m-2]!=0):\n",
    "                        x[i].append(1)\n",
    "                        max1+=1\n",
    "                    else:\n",
    "                        x[i].append(0)\n",
    "                else:\n",
    "                    x[i].append(0)\n",
    "        return max1\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[False]*len(s) for _ in range(len(s))]\n",
    "        count = 0\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = True\n",
    "            count += 1\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i+1, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j-i == 1:\n",
    "                        dp[i][j] = True\n",
    "                        count += 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                        if dp[i][j]:\n",
    "                            count += 1\n",
    "        return count\n",
    "        \n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        mem = [[] for _ in range(len(s))]\n",
    "        ans = 0\n",
    "        for ll in range(1, len(s)+1):\n",
    "            for start in range(0, len(s)):\n",
    "                end = start + ll - 1\n",
    "                if end >= len(s):\n",
    "                    break\n",
    "                if ll==1:\n",
    "                    mem[start].append(1)\n",
    "                    ans += 1\n",
    "                elif ll==2:\n",
    "                    if s[start] == s[end]:\n",
    "                        mem[start].append(1)\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        mem[start].append(0)\n",
    "                else:\n",
    "                    is_sol = (s[start]==s[end]) and mem[start+1][-2]\n",
    "                    if is_sol:\n",
    "                        mem[start].append(1)\n",
    "                        ans += 1\n",
    "                    else:\n",
    "                        mem[start].append(0)\n",
    "        return ans"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n=len(s)\n",
    "        d=[[0]*(n-i+1) for i in range(n)]\n",
    "        for i in range(n):\n",
    "            d[i][0]=1\n",
    "            d[i][1]=1\n",
    "        ans=n\n",
    "        for i in range(n-1,-1,-1):\n",
    "            for j in range(i+1,n):\n",
    "                if s[i]==s[j]:\n",
    "                    d[i][j-i+1]=d[i+1][j-1-i]\n",
    "                    ans+=d[i][j-i+1]\n",
    "        print(d)\n",
    "        return ans\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        if not s:   return 0\n",
    "        N = len(s)\n",
    "        dp = [[False]*N for _ in range(N)]\n",
    "        res = N\n",
    "        for i in range(N):\n",
    "            dp[i][i] = True\n",
    "        for ll in range(1,N):\n",
    "            for x in range(N-ll):\n",
    "                y = x+ll\n",
    "                if ll==1:\n",
    "                    dp[x][y] = (s[x]==s[y])\n",
    "                else:\n",
    "                    dp[x][y] = (dp[x+1][y-1] and s[x]==s[y])\n",
    "                \n",
    "                if dp[x][y]:\n",
    "                    res+=1\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[False] * len(s) for _ in range(len(s))]\n",
    "        result = 0\n",
    "        for i in range(len(s)-1, -1, -1): #注意遍历顺序\n",
    "            for j in range(i, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1: #情况一 和 情况二\n",
    "                        result += 1\n",
    "                        dp[i][j] = True\n",
    "                    elif dp[i+1][j-1]: #情况三\n",
    "                        result += 1\n",
    "                        dp[i][j] = True\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]* n for _ in range(n)]\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "        for l in range(n)[::-1]:\n",
    "            for r in range(l,n):\n",
    "                if s[l] == s[r]:\n",
    "                    if r - l <= 2:\n",
    "                        dp[l][r] = True\n",
    "                    else:\n",
    "                        dp[l][r] = dp[l+1][r-1]\n",
    "        return sum([sum(i) for i in  dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\r\n",
    "    # 代录 DP 从下到上 从左到右\r\n",
    "    def countSubstrings(self, s: str) -> int:\r\n",
    "        dp = [[False] * len(s) for _ in range(len(s))]\r\n",
    "        res = 0\r\n",
    "        for i in range(len(s) - 1, -1, -1):\r\n",
    "            for j in range(i, len(s)):\r\n",
    "                if s[i] == s[j]:\r\n",
    "                    if j - i <= 1:\r\n",
    "                        dp[i][j] = True\r\n",
    "                        res += 1\r\n",
    "                    else:\r\n",
    "                        if dp[i + 1][j - 1]:\r\n",
    "                            dp[i][j] = True\r\n",
    "                            res += 1\r\n",
    "        return res\r\n",
    "\r\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #dp[i][j]表示s[i,j+1]是否是回文子串\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        dp = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = [False] * n\n",
    "        \n",
    "        for j in range(n):\n",
    "            for i in range(j+1):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                    count += 1\n",
    "                elif j - i == 1 and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                    count += 1\n",
    "                elif j-1 >= 0 and i+1 <= n-1 and dp[i + 1][j - 1] and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                    count += 1\n",
    "\n",
    "        \n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #dp[i][j]表示s[i,j+1]是否是回文子串\n",
    "        n = len(s)\n",
    "        count = 0\n",
    "        dp = [0] * n\n",
    "\n",
    "        for i in range(n):\n",
    "            dp[i] = [False] * n\n",
    "        \n",
    "        for j in range(n):\n",
    "            for i in range(j+1):\n",
    "                if s[i] == s[j] and (j - i <= 1 or dp[i + 1]): \n",
    "                    dp[i] = True\n",
    "                    count += 1\n",
    "                else:\n",
    "                    dp[i] = False\n",
    "\n",
    "        return count\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "    "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "\n",
    "        n = len(s)\n",
    "        dp = [[False for _ in range(n+1)] for _ in range(n+1)]\n",
    "        for i in range(1, 1+n):\n",
    "            dp[i][i] = 1\n",
    "        res = n\n",
    "        for i in range(n, 0, -1):\n",
    "            for j in range(i+1, 1+n):\n",
    "                if s[i-1] == s[j-1]:\n",
    "                    dp[i][j] = dp[i+1][j-1] if j > i + 1 else True\n",
    "                    res += 1 if dp[i][j] else 0\n",
    "\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        result = 0\n",
    "        dp = [[False for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n - 1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if i == j:\n",
    "                    dp[i][j] = True\n",
    "                elif j - i <= 1 and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                elif s[i] == s[j] and dp[i + 1][j - 1]:\n",
    "                    dp[i][j] = True\n",
    "                \n",
    "                if dp[i][j]:\n",
    "                    result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        l = len(s)\n",
    "        dp = [[False]*(l+1) for i in range(l+1)]\n",
    "        res = 0\n",
    "        for li in range(1,l+1):\n",
    "            for i in range(l-li+1):\n",
    "                if li==1:\n",
    "                    dp[i][li]=True\n",
    "                elif i+1<l and li==2 and s[i]==s[i+1]:\n",
    "                    dp[i][li]=True\n",
    "                else:\n",
    "                    if s[i]==s[i+li-1]:\n",
    "                        dp[i][li]=dp[i+1][li-2]\n",
    "                if dp[i][li]==True:\n",
    "                    res+=1\n",
    "            print(dp[i])\n",
    "        return res\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[False]*(len(s) + 100) for _ in range(len(s) + 100)]\n",
    "        result = 0\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = True\n",
    "            result += 1\n",
    "\n",
    "        for i in range(len(s) - 1):\n",
    "            if s[i] == s[i + 1]:\n",
    "                dp[i][i + 1] = True\n",
    "                result += 1\n",
    "\n",
    "        for i in range(len(s) - 3, -1, -1):\n",
    "            for j in range(i + 2, len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1]\n",
    "                    if dp[i][j]:\n",
    "                        result += 1\n",
    "\n",
    "\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[False for _ in range(len(s))] for _ in range(len(s))]\n",
    "        count = len(s)\n",
    "        for i in range(len(s)-1):\n",
    "            dp[i][i] = True\n",
    "            if s[i]==s[i+1]: \n",
    "                dp[i][i+1] = True\n",
    "                count += 1\n",
    "        dp[-1][-1] = True\n",
    "        for i in range(len(s)-2,-1,-1):\n",
    "            for j in range(i+2,len(s)):\n",
    "                if dp[i+1][j-1] and s[i] == s[j]:\n",
    "                    dp[i][j] = True\n",
    "                    count += 1\n",
    "        for i in range(len(s)):\n",
    "            print(dp[i])\n",
    "        return count\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        len_ = len(s)\n",
    "        dp = [[0] * len_ for _ in range(len_)]\n",
    "        count = 0\n",
    "        for i in range(len_ - 1, -1, -1):\n",
    "            for j in range(i, len_):\n",
    "                if s[i] != s[j]:\n",
    "                    dp[i][j] = 0\n",
    "                else:\n",
    "                    if i == j:\n",
    "                        dp[i][j] = 1\n",
    "                        count += 1\n",
    "                    elif j - 1 == i:\n",
    "                        dp[i][j] = 1\n",
    "                        count += 1\n",
    "                    elif dp[i + 1][j - 1]:\n",
    "                        dp[i][j] = dp[i + 1][j - 1] + 1\n",
    "                        count += 1\n",
    "\n",
    "        return count"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        #dp[i][j]表示下标从i到j是不是回文子串，bool类型,i从0，j到len-1\n",
    "        dp = []\n",
    "        for i in range(len(s)):\n",
    "            dp.append([0]*len(s))\n",
    "\n",
    "        for i in range(len(s)-1,-1,-1):\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <=1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        if dp[i+1][j-1] == 1:\n",
    "                            dp[i][j] = 1\n",
    "                else:\n",
    "                    dp[i][j] = 0\n",
    "        res = []\n",
    "        for i in range(len(s)):\n",
    "            for j in range(i,len(s)):\n",
    "                res.append(dp[i][j])\n",
    "        n = 0\n",
    "        for _ in res:\n",
    "            if _ == 1:\n",
    "                n+=1\n",
    "        return n\n",
    "\n",
    "\n",
    "        "
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[1] for x in range(len(s))] # 以第i个字母结尾的回文子串长度\n",
    "        for i in range(1, len(s)):\n",
    "            if s[i-1] == s[i]:\n",
    "                dp[i].append(2)\n",
    "            for l in dp[i-1]:\n",
    "                if i-l-1 >= 0 and s[i-l-1] == s[i]:\n",
    "                    dp[i].append(l+2)\n",
    "        res = 0\n",
    "        for i in range(len(s)):\n",
    "            res += len(dp[i])\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        ans = 0\n",
    "        length = len(s)\n",
    "        #dp[i]表示以索引i为结尾 且是回文字符串的长度\n",
    "        dp = [[1] for _ in range(length)]\n",
    "        ans = 1\n",
    "        for index in range(1,length):\n",
    "            #判断是否可以组成两个数的回文串\n",
    "            if s[index] == s[index - 1]:\n",
    "                dp[index].append(2)\n",
    "            for k in dp[index - 1]:\n",
    "                if index - k > 0 and s[index] == s[index - k - 1]:\n",
    "                    dp[index].append(k + 2)\n",
    "            ans += len(dp[index])\n",
    "        return ans\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[0]*len(s) for x in range(len(s))]\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i,len(s)):\n",
    "                if s[i] == s[j]:\n",
    "                    if j - i <= 1:\n",
    "                        dp[i][j] = 1\n",
    "                        \n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "                        \n",
    "        return len([dp[x][y] for x in range(len(dp)) for y in range(len(dp)) if dp[x][y]])\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int: \n",
    "        n = len(s)\n",
    "        result = n\n",
    "        cache = {1: range(n) , 2 : []}\n",
    "        for i in range(0, n - 1): \n",
    "            if s[i] == s[i + 1]: \n",
    "                result += 1\n",
    "                cache[2].append(i)\n",
    "        for k in range(3, n + 1): \n",
    "            cache[k] = []\n",
    "            for i in cache[k - 2]: \n",
    "                if 0 < i < n + 2 - k and s[i - 1] == s[i + k - 2]: \n",
    "                    cache[k].append(i - 1)\n",
    "                    result += 1\n",
    "        return result"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        s = ' '+s\n",
    "        ret = [[]]\n",
    "        count = 0\n",
    "        for i in range(1,len(s)):\n",
    "            c_bin = [i]\n",
    "            count+=1\n",
    "            lastbin = ret[-1]\n",
    "            if s[i] == s[i-1]:\n",
    "                c_bin.append(i-1)\n",
    "                count+=1\n",
    "            for subs in lastbin:\n",
    "                if s[subs-1] == s[i]:\n",
    "                    c_bin.append(subs-1)\n",
    "                    count+=1\n",
    "            ret.append(c_bin)\n",
    "        return count\n",
    "\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "\n",
    "        # 方法1：暴力解法\n",
    "        # dp = [[0] * len(s) for _ in range(len(s))]\n",
    "        # dp[0][0] = 1\n",
    "        # for i in range(len(s)):\n",
    "        #     for j in range(i, len(s)):\n",
    "        #         if j - 1>=0:\n",
    "        #             sub_s = s[i: j+1]\n",
    "        #             if sub_s == sub_s[::-1]:\n",
    "        #                 dp[i][j] = dp[i][j-1] + 1\n",
    "        #             else:\n",
    "        #                 dp[i][j] = dp[i][j-1]\n",
    "        # print('dp: ', dp)\n",
    "        # return sum([d[-1] for d in dp])\n",
    "\n",
    "        # 更加动态规划的方法，我想起来了，只有头和尾的字母不同就不是回文字符串\n",
    "        # 代码随想录的作者采用bool的方法：\n",
    "\n",
    "        # 如果这矩阵是从上到下，从左到右遍历，那么会用到没有计算过的dp[i + 1][j - 1]，也就是根据不确定是不是回文的区间[i+1,j-1]，来判断了[i,j]是不是回文，那结果一定是不对的。\n",
    "\n",
    "        #所以一定要从下到上，从左到右遍历，这样保证dp[i + 1][j - 1]都是经过计算的。\n",
    "\n",
    "        dp = [[0] * len(s) for _ in range(len(s))]  # 这个模拟的是一个指针，而且是左右指针,需要特别注意边界\n",
    "        result = 0\n",
    "        for i in range(len(s)-1, -1, -1):\n",
    "            for j in range(i, len(s)):\n",
    "                if i == j:\n",
    "                    dp[i][j] = 1\n",
    "                    result += 1\n",
    "                elif j - i <= 2 and s[i] == s[j]:\n",
    "                    dp[i][j] = 1\n",
    "                    result += 1\n",
    "                elif s[i] == s[j] and j - i > 2:\n",
    "                    dp[i][j] = dp[i+1][j-1]\n",
    "                    result += 1 if dp[i+1][j-1] else 0\n",
    "\n",
    "        print('dp: ', dp)\n",
    "        \n",
    "        return result\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "\n",
    "        m = len(s) \n",
    "\n",
    "        dp = [[0 for _ in range(m)] for _ in range(m)]\n",
    "\n",
    "        for _ in range(m):\n",
    "            dp[_][_] = 1 \n",
    "        print('dp: ', dp)\n",
    "\n",
    "        for i in range(m, -1, -1):\n",
    "            for j in range(i + 1, m):\n",
    "                if j == i + 1 and s[i] == s[j]:\n",
    "                    dp[i][j] = 1\n",
    "                elif s[i] == s[j] and dp[i + 1][j - 1] == 1:\n",
    "                    dp[i][j] = 1 \n",
    "        \n",
    "        print('dp: ', dp)\n",
    "\n",
    "        return sum([sum(_) for _ in dp])"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        dp = [[0]*len(s) for _ in range(len(s))]\n",
    "        if not s:\n",
    "            return 0\n",
    "        for i in range(len(s)):\n",
    "            dp[i][i] = 1\n",
    "            if i<len(s)-1:\n",
    "                dp[i][i+1] = 1\n",
    "        for i in range(1, len(s)):\n",
    "            for j in range(0, i):\n",
    "                if s[i] == s[j] and dp[i-1][j+1]:\n",
    "                    dp[i][j] = 1\n",
    "        for i in range(len(s)-1):\n",
    "            dp[i][i+1] = 0\n",
    "        print(dp)\n",
    "        return sum(map(sum,dp))\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "\n",
    "        dp = [[0 for _ in range(n)] for _ in range(n)]\n",
    "        for i in range(n):\n",
    "            dp[i][i] = 1\n",
    "\n",
    "        res = n\n",
    "\n",
    "        for i in range(n - 2, -1, -1):\n",
    "            for j in range(i + 1, n):\n",
    "                if s[i] == s[j]:\n",
    "                    dp[i][j] = dp[i + 1][j - 1] if j - i > 1 else 1\n",
    "                    if dp[i][j]:\n",
    "                        res += 1\n",
    "        print(dp)\n",
    "        return res"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        length = len(s)\n",
    "        cnt = 0\n",
    "\n",
    "        dp = [[0 for j in range(length)] for i in range(length)]\n",
    "        for i in range(length):\n",
    "            dp[i][i] = 1\n",
    "            cnt += 1\n",
    "        \n",
    "        for l in range(1, length):\n",
    "            for start in range(length):\n",
    "                end = start+l\n",
    "                if end>=length:\n",
    "                    continue\n",
    "                if s[start]==s[end] and end-start==1:\n",
    "                    dp[start][end] = 1\n",
    "                    cnt += 1\n",
    "                elif s[start]==s[end] and dp[start+1][end-1]==1:\n",
    "                    dp[start][end] = 1\n",
    "                    cnt += 1\n",
    "        print(dp)\n",
    "        \n",
    "        return cnt"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        ans = 0\n",
    "        cache = [[0] * n for _ in range(n)]\n",
    "        def dfs(s, i, j):\n",
    "            if i > j:\n",
    "                return 1\n",
    "            if cache[i][j] != 0:\n",
    "                return cache[i][j]\n",
    "            cache[i][j] = dfs(s, i + 1, j - 1) if s[i] == s[j] else 0\n",
    "            return cache[i][j]\n",
    "        for i in range(n):\n",
    "            for j in range(i, n):\n",
    "                ans += dfs(s, i, j)\n",
    "\n",
    "        return ans\n",
    "\n"
   ]
  },
  {
   "cell_type": "code",
   "execution_count": null,
   "metadata": {},
   "outputs": [],
   "source": [
    "from typing import List\n",
    "import collections\n",
    "\n",
    "class Solution:\n",
    "    def countSubstrings(self, s: str) -> int:\n",
    "        n = len(s)\n",
    "        dp = [[0]*n for _ in range(n)]\n",
    "        for i in range(n-1, -1, -1):\n",
    "            for j in range(i, n):\n",
    "                if s[i] == s[j]:\n",
    "                    if j-i <= 1:\n",
    "                        dp[i][j] = 1\n",
    "                    else:\n",
    "                        dp[i][j] = dp[i+1][j-1]\n",
    "        return sum([j for i in dp for j in i])\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "\n",
    "                    \n"
   ]
  }
 ],
 "metadata": {},
 "nbformat": 4,
 "nbformat_minor": 2
}
